﻿/*
--------------------------------------
File: DecisionTree.cs
Project: Themaopdracht 7
Author: Unknown (vision course material, HU 2011 )
Adapted by: Roel Blaauwgeers
--------------------------------------
*/

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace THO7_Team8
{[Serializable]
    public class DecisionTree
    {
        public List<DataPoint> data;//all data points left in this tree;
        public DecisionTree leftChild;
        public DecisionTree rightChild;
        public Split split;
        public bool isForeground;

        public DecisionTree(List<DataPoint> d)
        {
            this.data = d;
            this.leftChild = null;
            this.rightChild = null;
            this.split = null;

            int fg = 0, bg = 0;

            foreach (DataPoint dp in data)
            {
                if (dp.classLabel == 1)
                {
                    fg++;
                }
                else
                {
                    bg++;
                }
            }

            if (fg >= bg)
            {
                isForeground = true;
            }
            else
            {
                isForeground = false;
            }
        }

        public double getGiniIndex()
        {
            if (this.leftChild == null)
            {//In the case of no kids
                //GiniIndex = #class1/total * #class2/total
                double class0Count = 0.0, class1Count = 0.0;
                int cl = -1;
                for (int i = 0; i < data.Count; i++)
                {
                    cl = this.data[i].classLabel;
                    if (cl == 0)
                        class0Count += 1.0;
                    else
                        class1Count += 1.0;
                }
                return (class0Count / data.Count) *
                    (class1Count / data.Count);
            }
            else
            {
                //GiniIndex = p(left)*gini(left)+p(right)*gini(right)
                double giniLeft = this.leftChild.getGiniIndex();
                double giniRight = this.rightChild.getGiniIndex();
                giniLeft *=
                    (double)this.leftChild.data.Count /
                     (double)this.data.Count;
                giniRight *=
                    (double)this.rightChild.data.Count /
                     (double)this.data.Count;
                return giniLeft + giniRight;
            }
        }

        public double getGiniIndex(double c0, double c1)
        {
            return c0 / (c0 + c1) * c1 / (c0 + c1);
        }

        public double getGiniIndex(double r0, double r1,
                double l0, double l1)
        {
            double total = r0 + r1 + l0 + l1;
            double totalLeft = l0 + l1;
            double totalRight = r0 + r1;
            return totalLeft / total * this.getGiniIndex(l0, l1) +
                totalRight / total * this.getGiniIndex(r0, r1);
        }

        public Split bestSplitForAtrributeFast(int attribute)
        {
            //Very inefficient method, writing an alternative 
            //might be nice.
            Split result = null;

            //Key should be the same in both of these.
            Dictionary<double, int> valuesBackgroundDic = new Dictionary<double, int>();
            Dictionary<double, int> valuesForegroundDic = new Dictionary<double, int>();

            for (int i = 0; i < data.Count; i++)
            {
                if (valuesBackgroundDic.ContainsKey(data[i].attributes[attribute]))
                {
                    if (data[i].classLabel == 0)
                    {
                        valuesBackgroundDic[data[i].attributes[attribute]] = ++valuesBackgroundDic[data[i].attributes[attribute]];
                    }
                    else
                    {
                        valuesForegroundDic[data[i].attributes[attribute]] = ++valuesForegroundDic[data[i].attributes[attribute]];
                    }
                }
                else
                {
                    if (data[i].classLabel == 0)
                    {
                        valuesBackgroundDic.Add(data[i].attributes[attribute], 1);
                        valuesForegroundDic.Add(data[i].attributes[attribute], 0);
                    }
                    else
                    {
                        valuesBackgroundDic.Add(data[i].attributes[attribute], 0);
                        valuesForegroundDic.Add(data[i].attributes[attribute], 1);
                    }
                }
            }

            //All these arrays indexes are bound to each other.
            double[] attributeKeys = new double[valuesBackgroundDic.Count];
            int[] attributeBackgroundValues = new int[valuesBackgroundDic.Count];
            int[] attributeForegroundValues = new int[valuesForegroundDic.Count];

            valuesBackgroundDic.Keys.CopyTo(attributeKeys, 0);
            valuesBackgroundDic.Values.CopyTo(attributeBackgroundValues, 0);
            valuesForegroundDic.Values.CopyTo(attributeForegroundValues, 0);

            for (int i = 1; i < attributeKeys.Length; i++)
            {
                double candidateSplit = (attributeKeys[i] + attributeKeys[i - 1]) / 2.0;
                double cntLeft0 = 0.0, cntLeft1 = 0.0;
                double cntRight0 = 0.0, cntRight1 = 0.0;
                for (int j = 0; j < attributeKeys.Length; j++)
                {
                    double a = attributeKeys[j];
                    if (a <= candidateSplit)
                    {
                        cntLeft0 += attributeBackgroundValues[j];
                        cntLeft1 += attributeForegroundValues[j];
                    }
                    else
                    {
                        cntRight0 += attributeBackgroundValues[j];
                        cntRight1 += attributeForegroundValues[j];
                    }
                }
                double giniIndexCandidate =
                    this.getGiniIndex(cntRight0, cntRight1,
                            cntLeft0, cntLeft1);
                Split candidate = new Split(attribute,
                        candidateSplit, giniIndexCandidate);
                if (result == null)
                {
                    result = candidate;
                }
                else
                {
                    if (result.giniIndex > candidate.giniIndex)
                    {
                        result = candidate;
                    }
                }
            }

            return result;
        }

        public Split bestSplitForAtrribute(int attribute)
        {
            //Very inefficient method, writing an alternative 
            //might be nice.
            Split result = null;
            double[] valuesAttribute = new double[this.data.Count];
            for (int i = 0; i < data.Count; i++)
            {
                valuesAttribute[i] = data[i].attributes[attribute];
            }
            Array.Sort(valuesAttribute);
            for (int i = 1; i < data.Count; i++)
            {
                if (valuesAttribute[i] != valuesAttribute[i - 1])
                {
                    double candidateSplit =
                       (valuesAttribute[i] + valuesAttribute[i - 1]) / 2.0;
                    double cntLeft0 = 0.0, cntLeft1 = 0.0;
                    double cntRight0 = 0.0, cntRight1 = 0.0;
                    for (int j = 0; j < data.Count; j++)
                    {
                        double a = data[j].attributes[attribute];
                        int c = data[j].classLabel;
                        if (a <= candidateSplit)
                        {
                            if (c == 0)
                            {
                                cntLeft0 += 1.0;
                            }
                            else
                            {
                                cntLeft1 += 1.0;
                            }
                        }
                        else
                        {
                            if (c == 0)
                            {
                                cntRight0 += 1.0;
                            }
                            else
                            {
                                cntRight1 += 1.0;
                            }
                        }
                    }
                    double giniIndexCandidate =
                        this.getGiniIndex(cntRight0, cntRight1,
                                cntLeft0, cntLeft1);
                    Split candidate = new Split(attribute,
                            candidateSplit, giniIndexCandidate);
                    if (result == null)
                    {
                        result = candidate;
                    }
                    else
                    {
                        if (result.giniIndex > candidate.giniIndex)
                        {
                            result = candidate;
                        }
                    }
                }
            }
            return result;
        }

        public Split bestSplitAvailable()
        {
            Split result = null;
            int noOfAttributes = data[0].noOfAttributes;
            for (int i = 0; i < noOfAttributes; i++)
            {
                Split candidate = this.bestSplitForAtrributeFast(i);
                if (result == null)
                {
                    result = candidate;
                    //System.out.println(candidate);
                }
                else
                {
                    if (candidate != null)
                    {
                        //System.out.println(candidate);
                        if (result.giniIndex > candidate.giniIndex)
                        {
                            result = candidate;
                        }
                    }
                    else
                    {
                        //System.out.println("no split for attribute "+i);
                    }
                }
            }
            return result;
        }

        public void executeSplit(Split s)
        {
            this.split = s;
            List<DataPoint> leftData = new List<DataPoint>();
            List<DataPoint> rightData = new List<DataPoint>();

            foreach (DataPoint dp in data)
            {
                if (dp.attributes[s.attributeNoSplit] >= s.valueSplit)
                {
                    leftData.Add(dp);
                }
                else
                {
                    rightData.Add(dp);
                }
            }

            this.leftChild = new DecisionTree(leftData);
            this.rightChild = new DecisionTree(rightData);
        }

        public void partitionRecursively(int minDataPoints)
        {
            //minDataPoints is a stop condition, if there are
            //too little data points, we want to stop. Why?

            if (this.data.Count > minDataPoints)
            {
                double giniNow = this.getGiniIndex();
                Split s = this.bestSplitAvailable();
                if (s != null && giniNow > s.giniIndex)
                {
                    executeSplit(s);
                    Console.WriteLine("Split: " + leftChild.data.Count + " , " + rightChild.data.Count);

                    leftChild.partitionRecursively(minDataPoints);
                    rightChild.partitionRecursively(minDataPoints);
                }
            }
        }

        public Boolean isForegroundPixel(double[] features)
        {
            if (features[this.split.attributeNoSplit] >= this.split.valueSplit)
            {
                if (leftChild.split != null)
                {
                    return leftChild.isForegroundPixel(features);
                }
                else
                {
                    return leftChild.isForeground;
                }
            }
            else
            {
                if (rightChild.split != null)
                {
                    return rightChild.isForegroundPixel(features);
                }
                else
                {
                    return rightChild.isForeground;
                }
            }
        }

        public void removeDataPoints()
        {
            this.data = null;
            if (leftChild != null)
            {
                leftChild.removeDataPoints();
                rightChild.removeDataPoints();
            }
        }

    }
}
